package genetic.q1;

import java.util.Collections;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.Vector;

import genetic.Genotype;
import genetic.Phenotype;

public class TSPPhenotype extends Phenotype{

	int size;
	TSPGraph graph;

	public TSPPhenotype(int size, TSPGraph g){
		this.size = size;
		this.graph = g;
	}

	@Override
	public List<Genotype> getInitialPopulation(int populationSize) {
		return getInitialRandomPopulation(populationSize);
		//		return new TSPGreedy(graph).getPopulation(populationSize);
	}

	@Override
	public Genotype createRandomInstance() {
		return new TSPGenotype(getRandomIntString(size,0), graph);
	}

	@Override
	public Genotype[] crossover(Genotype g1, Genotype g2) {
		//		int[][] kids = customCrossover(g1.getIntString(), g2.getIntString());
		int[][] kids = cycleCrossover(g1.getIntString(), g2.getIntString());
		//		int[][] kids = pmxCrossover(g1.getIntString(), g2.getIntString());
		//		int[][] kids = order1crossover(g1.getIntString(), g2.getIntString());
		return new Genotype[]{new TSPGenotype(kids[0], graph), new TSPGenotype(kids[1], graph)};
	}

	//crossover
	protected int[][] customCrossover(int[] p1, int[] p2){
		int[][] kids = new int[2][p1.length];
		int[] rand = getRandomPair(p1.length);

		Set<Integer> tmp1 = new TreeSet<Integer>();
		Set<Integer> tmp2 = new TreeSet<Integer>();
		for (int i=rand[0]; i<=rand[1]; i++){
			kids[0][i] = p1[i];
			tmp1.add(p1[i]);
			kids[1][i] = p2[i];
			tmp2.add(p2[i]);
		}
		int index0 = -1;
		int index1 = -1;
		for (int i=0; i<p2.length; i++){
			if (p2[i]==p1[rand[1]] && index0==-1){
				index0 = (i+1) % p1.length;
			}
			if (p1[i]==p2[rand[1]] && index1==-1){
				index1 = (i+1) % p1.length;
			}
		}
		int index = (rand[1]+1) % p1.length;
		while (index!=rand[0]){
			int city = getClosestCity(tmp1, kids[0][(index-1+p1.length) % p1.length], p2);
			tmp1.add(city);
			kids[0][index] = city;
			index = (index + 1) % p1.length;
		}
		index = (rand[1]+1) % p1.length;
		while (index!=rand[0]){
			int city = getClosestCity(tmp2, kids[1][(index-1+p1.length) % p1.length], p1);
			tmp2.add(city);
			kids[1][index] = city;
			index = (index + 1) % p1.length;
		}
		//		int index = (rand[1]+1) % p1.length;
		//		while(index!=rand[0]){
		//			if (!tmp1.contains(p2[index0])){
		//				tmp1.add(p2[index0]);
		//				kids[0][index] = p2[index0];
		//				index = (index+1) % p1.length;
		//			}
		//			index0 = (index0+1) % p1.length;
		//		}
		//		index = (rand[1]+1) % p1.length;
		//		while(index!=rand[0]){
		//			if (!tmp2.contains(p1[index1])){
		//				tmp2.add(p1[index1]);
		//				kids[1][index] = p1[index1];
		//				index = (index+1) % p1.length;
		//			}
		//			index1 = (index1 +1) % p1.length;
		//		}
		return kids;
	}

	private int getClosestCity(Set<Integer> forbidden, int city, int[] genome){
		int index = -1;
		for (int i=0; i<genome.length; i++){
			if (genome[i] == city){
				index = i;
				break;
			}
		}
		for (int i=0; i<genome.length/2+1; i++){
			if (!forbidden.contains(genome[(index+i) % genome.length])){
				return genome[(index+i) % genome.length];
			} else if (!forbidden.contains(genome[(index-i+genome.length) % genome.length])){
				return genome[(index-i+genome.length) % genome.length];
			}
		}
		while (true) System.out.println("FFFFFFFFFFFFFFFFFFFFFFF");
		//		return -1;
	}

	@Override
	public double fitness(Genotype g) {
		int[] rep = g.getIntString();
		int length = graph.getDistance(rep[rep.length-1]-1, rep[0]-1);
		for (int i=0; i<rep.length-1; i++){
			length = length + graph.getDistance(rep[i]-1, rep[i+1]-1);
		}
		return graph.maxArc / (double)length * 100.0;
	}

	@Override
	public List<Genotype> getMatingPool(List<Genotype> population,
			int populationSize) {
		return getMatingPoolRouletteWheel(population, populationSize);
		//		return getMatingPoolRandom(populationSize);
		//		return getMatingPoolTournamentSelection(population, populationSize, 2, 1, 1);
	}

	@Override
	public Genotype mutate(Genotype g, double Pm) {
		if (Math.random()<Pm){
			return new TSPGenotype(customMutation(g.getIntString()), graph);
			//			return new TSPGenotype(swapMutation(g.getIntString()), graph);
			//			return new TSPGenotype(inverseMutation(g.getIntString()), graph);
			//			return new TSPGenotype(scrambleMutation(g.getIntString()), graph);
		} else {
			return g;
		}
	}

	protected int[] customMutation(int[] org){
		int[] ans = new int[org.length];
		int city1 = (int)(Math.random()*org.length);
		//		int numCities = (int)(org.length/6.0);
		int numCities = 5;

		Vector<Integer> minCities = new Vector<Integer>();
		int index = 0;
		while(minCities.size()<numCities){
			if (Math.abs(index-city1)>1){
				minCities.add(index);
			}
			index++;
		}
		for (int i=0; i<org.length; i++) if (Math.abs(i-city1)>1){			//find the minimum 6 cities
			//assumes distances are the same for both ways

			//insert each of the elements to the vector and removes the maximal one
			//that way the vector always has 6 cities
			minCities.add(i);
			int max = 0;
			int minCity = 0;
			for (int j=0; j<minCities.size(); j++){
				if (max < graph.getDistance(org[minCities.get(j)]-1, org[city1]-1)){
					max = graph.getDistance(org[minCities.get(j)]-1, org[city1]-1);
					minCity = j;
				}
			}
			minCities.remove(minCity);
		}
		Collections.shuffle(minCities);
		int city2 = minCities.remove(0);

		for (int i=0; i<=Math.min(city1, city2-1); i++){
			ans[i] = org[i];
		}
		int num;
		if (city1<city2){
			num = 1;
		} else {
			num =-1;
		}
		ans[city1+num] = org[city2];

		for (int i=Math.min(city1+2, city2); i<=Math.max(city1-2,city2); i++){
			ans[i] = org[i-num];
		}
		for (int i=Math.max(city1,city2+1); i<org.length; i++){
			ans[i] = org[i];
		}
		//		System.out.println(city1 +","+ city2 +","+ Arrays.toString(ans));
		return ans;

	}

	@Override
	public void updateFitness(List<Genotype> population) {
	}

}
